/*
 * Copyright (C), 2015-2018
 * FileName: Solution104
 * Author:   zhao
 * Date:     2018/9/9 13:50
 * Description: 104. 二叉树的最大深度
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredtwo;

import com.lizhaoblog.diynode.TreeNode;

/**
 * 〈一句话功能简述〉<br>
 * 〈104. 二叉树的最大深度〉
 *
 * @author zhao
 * @date 2018/9/9 13:50
 * @since 1.0.1
 */
public class Solution104 {
  /**************************************
   * 题目
   给定一个二叉树，找出其最大深度。
   二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
   说明: 叶子节点是指没有子节点的节点。

   示例：
   给定二叉树 [3,9,20,null,null,15,7]，

   3
   / \
   9  20
   /  \
   15   7
   返回它的最大深度 3 。
   *************************************/

  /**************************************
   *
   * 想法：
   *    递归往下，同时传递一个深度变量
   *
   * 我的做法
   *    超过100.00%的测试案例
   * 总结：
   *    不需要传递深度变量，直接根据返回值进行判断
   * ***********************************/
  public int maxDepth(TreeNode root) {
    if (root == null) {
      return 0;
    }

    return recDepth(root, 1);
  }

  private int recDepth(TreeNode root, int depth) {
    if (root == null) {
      return depth - 1;
    }

    if (root.left == null && root.right == null) {
      return depth;
    }
    depth++;
    int leftDepth = recDepth(root.left, depth);
    int rightDepth = recDepth(root.right, depth);
    return Math.max(leftDepth, rightDepth);
  }

  /**************************************
   * 比我好的答案
   * ***********************************/
  public int better(TreeNode root) {
    // return 0 for null node
    if (root == null) {
      return 0;
    }
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    // return depth of the subtree rooted at root
    return Math.max(leftDepth, rightDepth) + 1;
  }

}
